package arrayList;

import java.util.ArrayList;
import java.util.Random;


/**
 * This class does not handle duplicates 
 * @author ldong
 *
 * @param <T>
 */
public class SkipList<T extends Comparable<? super T>>
{
    public ArrayList<ArrayList<T>> cols;
    public ArrayList<T> base;
    
    /******************************************/
    public SkipList()
    {
    	cols = new ArrayList<ArrayList<T>>();
    	base = new ArrayList<T>();
    	cols.add(base);  // add the base level to the cols as 0 level
    }
    /******************************************/
    /******************************************/
    /******************************************/
    /******************************************/
    /******************************************/
    
    
    /************All Layer Controller**********/

    
    public boolean add(T value)
    {
    	/* could do a search on base here */
    	int level = buildLevel();
  
		if(!find(value))
	    	for(int j = 0; j< level; j++)
	    	{ 	
	    		// make a new layer if necessary
	    		if(cols.size() < level)
		    		makeNewLevel();

	    		levelAdd(j, value);
	    	}// end of for loop
	    	
    	return true;
    	
    }
    
    public boolean find(T value)
    {
    	for(int i = cols.size()-1; i >= 0; i--)
    	{
    		// once it found, return true and exit it
    		if(levelFind(i, value))
    			return true;
    	}
    	
    	return false;
    }
    
    // remove certain value
    public boolean remove(T value)
    {
    	boolean mark = false;
    	for(int i = cols.size()-1; i >= 0; i--)
    	{
    		// if it could be removed, mark it true for removed
    		if(cols.get(i).remove(value))
    			mark = true;
    	}
    	return mark;
    }

    
    // reset all layers
    public void reset()
    {
    	for(int i = 0; i< cols.size(); i++)
    		levelReset(i);
    }
    
    // reset everything
    public void resetAll()
    {
    		cols.clear();
    }
    
    // print out everthing
    public void print()
    {
    	
    	
//    	for(int i = cols.size(); i > 0; i--)
//    	{
//    		System.out.print("Level "+ i + ": ");
//    	    levelPrintClean(i-1);
//    	}
    	
//    	 works perfectly fine
    	for(int i = cols.size(); i > 0; i--)
    	{
    	    levelPrint(i-1);
    	}
    }
    
    /******** Base Layer Controller ***********/

	  public void baseAdd(T value)
	  {
	  	// if not found
	  	if(!baseFind(value))
	  	{	
	  		// add it
	  		if(base.size() == 0)
					base.add(value);
	  		else
	    		for(int i= 0; i < base.size(); i++)
	    		{
	    			if(value.compareTo(base.get(i)) < 0)
	    			{
	    				base.add(i, value);
	    				return;
	    			}
	    			else if(value.compareTo(base.get(i)) > 0)
	    			{
	    				base.add(value);
	    				return;
	    			}
	    		}
	  	}
	  	else
	  		System.out.println("Sorry, it existed already.");
	  }
	  
		public void printbase()
		{
			System.out.println(base);
		}
		
	  public boolean baseFind(T value)
	  {
	  	return base.contains(value);
	  }
	  
	  public int baseCompare(T value)
	  {
		  return base.size() - 1 - base.indexOf(value);
	  }
		
	   /******** Layer Controller ***********/

	   /*  These methods supposed to be private
	    *  however for debug purpose
	    *  they are all public
	    **/ 
	  public void makeNewLevel()
	  {
	      ArrayList<T> temp =  new ArrayList<T>();
		  cols.add(temp);
	  }
	  
	  public void levelAdd(Integer level, T value)
	  {
    	// if not found
    	if(!levelFind(level,value))
    	{	
    		// add it if size is 0
    		if(cols.get(level).size() == 0)
    			cols.get(level).add(value);
    		else
	    		for(int i= 0; i < cols.get(level).size(); i++)
	    		{
	    			if(value.compareTo(cols.get(level).get(i)) < 0)
	    			{
	    				cols.get(level).add(i, value);
	    				return;
	    			}
	    			else if(value.compareTo(cols.get(level).get(i)) > 0)
	    			{
	    				cols.get(level).add(value);
	    				return;
	    			}
	    		}// end of for
    	}
    	else
    		System.out.println("Sorry, "+value
    				+" existed already in Level " + level);

    }
    
	public void levelPrint(Integer level)
	{
		System.out.print("Level "+ level + ":   ");
		for(int i = 0; i< cols.get(level).size(); i++)
			System.out.print(cols.get(level).get(i)+ "   ");
		System.out.println();
		
//		System.out.println(cols.get(level));  // this one prints as set
	}
	
	
	public void levelPrintClean(Integer i)
	{
		// left column, level mark
    	System.out.print("Level "+ i + ": ");
    
	   	for(int j = 0; i< cols.get(i).size(); j++)
	   	{
	   		levelCompare(i-1, cols.get(i).get(j));
	   	}
        	
	}
	
	 // compare value to certain layer and get the difference
	 public int levelCompare(int i, T value)
	 {
		  return cols.get(i).size() - 1 - cols.get(i).indexOf(value);
     }
	
	 public boolean levelFind(Integer level, T value)
	 {
    	return cols.get(level).contains(value);
	 }
    
	 public boolean levelRemove(Integer level, T value)
	 {
    	return cols.get(level).remove(value);
	 }
    
    public void levelReset(Integer level)
    {
    	 cols.get(level).clear();
    }
    /*******************************************/
    
    
	  private boolean odds()
	  {
	  	Random rand = new Random(); 
	  	return rand.nextBoolean();		
	  }
	  
	  public int buildLevel()
	  {
	  	int level = 0;
	  	while(odds())
	  		level++;
	  	return level;
	  }
	  
	  public String printSpace(int number)
	  {
		  String temp = "";
		  for(int j = 0; j< number; j++)
			  temp +="    ";
		  return temp;
	  }
	  /*******************************************/

    
}
